A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form.
Certain devices within the network referred to as routers use routing protocols to exchange and accumulate topology information that describes the network. This allows a router to construct its own routing topology map of the network. Upon receiving an incoming data packet, the router examines keying information within the packet and forwards the packet in accordance with the accumulated topology information.
Many routing protocols use flooding-based distribution mechanisms to announce topology information to routers within the network. These routing protocols typically rely on routing algorithms that require each of the routers to have synchronized routing topology information. For example, Open Shortest Path First (OSPF) and Intermediate system to intermediate system (IS-IS) routing protocols are link state protocols that use link state messages to ensure their routing topology is synchronized with respect to available interfaces, metrics and other variables associated with network links. For example, OSPF utilizes Link State Advertisements (LSAs) while IS-IS uses Link State protocol data units (LSPs) to exchange information.
A router generating a link state message typically floods the link state message throughout the network such that every other router receives the link state message. In network topologies where routers are connected by point-to-point connections, each router floods link state messages to adjacent routers reachable on each interface to ensure synchronization. In networks using multi-access media, such as an Ethernet network, the routers within the network flood the link state messages to all other routers. In either case, the receiving routers construct and maintain their own network topologies using the link information received via the link state messages.
In some cases, routers are configured to periodically broadcast link state messages to other routers within a network such that all routers in the network maintain synchronized link state databases (representative of topology information). As the network grows larger, these link state messages can become burdensome for the routers in the network. Efforts have been made to reduce the impact of such link state messages for the purpose of refreshing the databases of the routers, for example, by reducing the number of link state messages that are sent.